package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC955 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minDeletionSize(String[] strs) {
            int m = strs.length, n = strs[0].length(), needRemoveCnt = 0, curEqualCnt = 0, prevMatchCol = 0;
            int[] rowSituation = new int[m]; // 0 mean init, 1 mean ok(great than prev line), 2 mean equal to prev line.
            for (int i = 0; i < n; i++) {
                boolean curColIsThrough = true;
                for (int j = 1; j < m; j++) {
                    // j indicate row
                    if (strs[j].charAt(i) < strs[j - 1].charAt(i)) {
                        if (rowSituation[j] != 1) {
                            ++needRemoveCnt;
                            ++curEqualCnt;
                            if (rowSituation[j] == 0) {
                                for (int k = j - 1; k >= 1; k--) {
                                    rowSituation[k] = 0;   // init situation need to revert all to start.
                                }
                            } else {
                                // prev is equal here
                                for (int k = j - 1; k >= 1; k--) {
                                    rowSituation[k] = (strs[k].charAt(prevMatchCol) == strs[k - 1].charAt(prevMatchCol)) ? 2 : 1;
                                }
                            }

                            curColIsThrough = false;
                            break;
                        }
                    } else if (strs[j].charAt(i) == strs[j - 1].charAt(i)) {
                        if (rowSituation[j] != 1) {
                            rowSituation[j] = 2;
                            curEqualCnt++;
                        }
                    } else {
                        rowSituation[j] = 1;
                    }
                }

                if (curEqualCnt == 0) break;
                else curEqualCnt = 0;
                if (curColIsThrough) prevMatchCol = i;
            }

            return needRemoveCnt;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.minDeletionSize(new String[]{"ca", "bb", "ac"}));   // 1
        System.out.println(solution.minDeletionSize(new String[]{"xc", "yb", "za"}));   // 0
        System.out.println(solution.minDeletionSize(new String[]{"zyx", "wvu", "tsr"}));    // 3
        System.out.println(solution.minDeletionSize(new String[]{"abx", "agz", "bgc", "bfc"})); // 1
        System.out.println(solution.minDeletionSize(new String[]{"vdy", "vei", "zvc", "zld"})); // 2
    }

    public static void main(String[] args) throws Exception {
        LC955 an = new LC955();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
